#include <bits/stdc++.h>

using namespace std;

// 判断链表是否是回文结构
// 测试链接 : https://leetcode.cn/problems/palindrome-linked-list/

// 不需要提交这个类
struct ListNode 
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

// 提交这个类即可
class Solution 
{
public:
    bool isPalindrome(ListNode* head) 
    {
        if(head == nullptr || head->next == nullptr) return true;
        // 找中点
        ListNode *slow = head, *fast = head;            
        // 1->2->2->1->null，中点是第一个 2 的位置
        // 1->2->3->2->1->null，中点是 3 的位置
        while(fast->next != nullptr && fast->next->next != nullptr)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        // 现在中点就是slow，从中点开始往后的节点逆序
        ListNode *pre = slow;
        ListNode *cur = pre->next;
        ListNode *next = nullptr;
        pre->next = nullptr;
        while(cur != nullptr)
        {
            next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        // 上面的过程已经把链表调整成从左右两侧往中间指
		// head -> ... -> slow <- ... <- pre
        bool ans = true;
        ListNode *left = head;
        ListNode *right = pre;
        while(left != nullptr && right != nullptr)
        {
            if(left->val != right->val)
            {
                ans = false;
                break;
            }
            left = left->next;
            right = right->next;
        }
        // 本着不坑的原则，把链表调整回原来的样子再返回判断结果
        cur = pre->next;
        pre->next = nullptr;
        next = nullptr;
        while(cur != nullptr)
        {
            next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return ans;
    }
};


// 提交这个类即可
class Solution 
{
public:
    // 找出链表的中间节点，偶数长度的链表则返回第二个
    // 1->2->2->1->null，中点是第二个 2 的位置
    // 1->2->3->2->1->null，中点是 3 的位置
    ListNode* findMid(ListNode* head)
    {
        ListNode *slow = head, *fast = head;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

    // 反转链表，并返回反转后的头节点
    ListNode* reverseList(ListNode *head)
    {
        ListNode *newHead = nullptr;
        ListNode *cur = head;
        while(cur)
        {
            ListNode *next = cur->next;
            cur->next = newHead;
            newHead = cur;
            cur = next;
        }
        return newHead;
    }

    bool isPalindrome(ListNode* head) 
    {
        if(!head || !head->next) return true;
        ListNode* mid = findMid(head);
        ListNode* rHead = reverseList(mid);
        // 1->2->2->1->null => head:1->2->2->null rHead:1->2->null
        // 1->2->3->2->1->null => head:1->2->3->null rHead:1->2->3->null
        // 注：此代码没有恢复原来的链表关系
        while(head && rHead)
        {
            if(head->val != rHead->val) return false;
            head = head->next;
            rHead = rHead->next;
        }
        return true;
    }
};